Product Code Database
The Smith set, sometimes called the top-cycle generalizes the idea of a Condorcet winner to cases where no such winner exists. It does so by allowing cycles of candidates to be treated jointly, as if they were a single Condorcet winner. Voting systems that always elect a candidate from the Smith set pass the Smith criterion. The Smith set and Smith criterion are both named for mathematician John H. Smith.
The Smith set provides one standard of optimal choice for an election outcome. An alternative, stricter criterion is given by the Landau set.
Alternatively, it can be defined as the set of all candidates with a (non-strict) beatpath to any candidate who defeats them.
A set of candidates each of whose members pairwise defeats every candidate outside the set is known as a dominating set. Thus the Smith set is also called the smallest dominating set.
The Smith set can be constructed from the Schwartz set by repeatedly adding two types of candidates until no more such candidates exist outside the set:
Note that candidates of the second type can only exist after candidates of the first type have been added.
Proof: Suppose on the contrary that there exist two dominating sets, D and E, neither of which is a subset of the other. Then there must exist candidates such that and But by hypothesis d defeats every candidate not in D (including e) while e defeats every candidate not in E (including d), a contradiction. ∎
Corollary: It follows that the Smith set is the smallest non-empty dominating set, and that it is well defined.
Theorem: If D is a dominating set, then there is some threshold θ D such that the elements of D are precisely the candidates whose Copeland scores are at least θ D. (A candidate's Copeland score is the number of other candidates whom he or she defeats plus half the number of other candidates with whom he or she is tied.)
Proof: Choose d as an element of D with minimum Copeland score, and identify this score with θ D. Now suppose that some candidate has a Copeland score not less than θ D. Then since d belongs to D and e doesn't, it follows that d defeats e; and in order for es Copeland score to be at least equal to ds, there must be some third candidate f against whom e gets a better score than does d. If then we have an element of D who does not defeat e, and if then we have a candidate outside of D whom d does not defeat, leading to a contradiction either way. ∎
Though less common, the term Smith-efficient has also been used for methods that elect from the Smith set.
Here is an example of an electorate in which there is no Condorcet winner: There are four candidates: A, B, C and D. 40% of the voters rank D>A>B>C. 35% of the voters rank B>C>A>D. 25% of the voters rank C>A>B>D. The Smith set is {A,B,C}. All three candidates in the Smith set are majority-preferred over D (since 60% rank each of them over D). The Smith set is not {A,B,C,D} because the definition calls for the smallest subset that meets the other conditions. The Smith set is not {B,C} because B is not majority-preferred over A; 65% rank A over B. (Etc.)
In the example above, the three candidates in the Smith set are in a "rock/paper/scissors" majority cycle: A is ranked over B by a 65% majority, B is ranked over C by a 75% majority, and C is ranked over A by a 60% majority.
For example, the voting method Smith//Minimax applies Minimax to the candidates in the Smith set. Another example is the Tideman alternative method, which alternates between eliminating candidates outside of the Smith set, and eliminating the candidate who was the plurality loser (similar to instant-runoff), until a Condorcet winner is found. A different approach is to elect the member of the Smith set that is highest in the voting method's order of finish.
Methods failing the Condorcet criterion also fail the Smith criterion. However, some Condorcet methods (such as Minimax) can fail the Smith criterion.
It also contains the Banks set and the Bipartisan set. A number of other subsets of the Smith set have been defined as well.
The algorithm to compute the Smith set is agglomerative: it starts with the Copeland set, which is guaranteed to be a subset of it but will often be smaller, and adds items until no more are needed. The first step is to sort the candidates according to score:
Now we look at any new cells which need to be considered, which are those below the top-left square containing {A,D,G}, but excluding those in the first two columns which we have already accounted for. The cells which need attention are shaded pale blue. As before we locate the positionally lowest non-zero entry among the new cells, adding all rows down to it, and all rows with the same score as it, to the expanded set, which now comprises {A,D,G,C}.
We repeat the operation for the new cells below the four members which are known to belong to the Smith set. These are shaded pink, and allow us to find any candidates not defeated by any of {A,D,G,C}. Again there is just one, F, whom we add to the set.
The cells which come into consideration are shaded pale green, and since all their entries are zero we do not need to add any new candidates to the set, which is therefore fixed as {A,D,G,C,F}. And by noticing that all the entries in the black box are zero, we have confirmation that all the candidates above it defeat all the candidates within it.
The following C function illustrates the algorithm by returning the cardinality of the Smith set for a given doubled results matrix r and array s of doubled Copeland scores. There are n candidates; ri j is 2 if more voters prefer i to j than prefer j to i, 1 if the numbers are equal, and 0 if more voters prefer j to i than prefer i to j ; si is the sum over j of the ri j . The candidates are assumed to be sorted in decreasing order of Copeland score. int row, col, lhs, rhs;
for (rhs = 1, lhs = 0; lhs < rhs; lhs = rhs, rhs = row + 1) {
for (; rhs < n && s[rhs] == s[rhs - 1]; rhs++); /* this line optional */
for (col = rhs, row = n; col == rhs && row >= rhs; row--)
for (col = lhs; col < rhs && r[row - 1][col] == 0; col++);
}
return lhs;
}
|
|
